Robots and Autonomous/Unmanned driving vehicles are two wide areas and systems affecting everyday life nowadays. Robots are used for industrial automation or for living assistance. Recently also drones have been introduced for military and civilian applications. Autonomous driving cars have shown high level of reliability and in the near future will be available for public use, while they are already used for non-public road use, as agriculture and mining application. Unmanned vehicles are also envisaged for crewless ships or spacecraft.
Other areas of applications include the medical sector when chirurgical instruments shall be moved among hard and soft tissues and vital organs. Other applications include military and space application where vehicles need to be moved avoiding obstacles.
For the above reasons the path or movement of such an object has to be planned including avoiding of obstacles. Path Planning is the area of Robotics devoted to the generation of a path between a starting state to a target final state set. The path shall consider robot/vehicle constraints and state evolution dynamics and shall live in the obstacle free set of state of the robot/vehicle.
In U.S. Pat. No. 7,447,593 B2 a path planning system and method for an object such as a vehicle is disclosed. The system provides a randomized adaptive path planning handling real-time path planning for a vehicle operating under kinodynamic constraints in dynamically changing and uncertain environments with probabilistic knowledge of vehicle and obstacle movement. In detail a tree built is performed by the following steps: Setting a root node to an initial vehicle state and checking if stopping conditions are satisfied. If not, perform a deterministic tree extension and a random tree extension. Based on the tree extensions a node is chosen that has not yet been chosen. Then it is checked whether the node has be extended or not. If not then the node is set to dead. If the node has been extended then it is checked whether kill conditions are satisfied or not and if the kill conditions are not satisfied then it is checked whether all nodes have been chosen or not. If not all nodes have been chosen, the node that has not been yet chosen is chosen. Otherwise it is again checked whether the stopping conditions are satisfied or not.
In U.S. Pat. No. 5,999,881 an automatic part planning system and method is disclosed. The system and method automatically finds collision-free part removal paths. The system sparsely samples the high-dimensional state space and maps the rest of the space using proximity assumptions. In more detail U.S. Pat. No. 5,999,881 checks whether a path connecting the start and destination states being totally contained within overlapping regions defined by spheres around the start state and the destination state is tested to determine if it collides with an obstacle. If an obstacle is encountered then the collision point where the obstacle intersects the region is determined and the current region and neighbor regions are adapted in their size such that the distance between its center to a closest collision point is lower. Then an obstacle free region is chosen as parent region from which to spawn a child region. The candidate point with the parent region is chosen as a center point of a child region and if the candidate point hits an obstacle then the radii of the regions are appropriately adjusted and a further candidate point or parent region is chosen repeatedly. If the candidate point does not hit an obstacle then a child region is created with a candidate point as its center point having a radius being less than the closest collision location in a list of collision points.
In WO 2006/080996 A2 a point-to-point path planning method is disclosed for determining a path for a vehicle, wherein a starting point and a termination point are defined and an obstacle detector detects one or more obstacles in a work area between the starting point and the termination point. A boundary zone is defined about each corresponding obstacle. Then candidate paths are identified between the starting point and the termination point. Each candidate path only intersects each boundary zone, one for each corresponding obstacle. An economic cost is estimated for traversing each candidate path or a portion thereof between the starting point and the termination point. A preferential path is selected from the identified candidate paths based on the preferential path being associated with the lowest estimated economic cost.
Other path planning methods and algorithms are for example disclosed in the non-patent literature of S. Karaman, E. Frazzoli, “Sampling-based algorithms for optimal motion planning”, Int. J. of Robotics Research 30(7): 846-894, 2011 or in the non-patent literature of Webb, D. and van den Berg, J. (2013), “Kinodynamic RRT: Asymptotically optimal motion planning for robots with linear dynamics”, pp. 5054-5061.